/*************************************************************************
	> File Name: two_eggs.cpp
	> Author: likang
	> Mail: likang@ict.ac.cn
	> Created Time: 二  9/13 21:17:12 2016
 ************************************************************************/

//假设有m个鸡蛋，n层楼，找出恰好使鸡蛋碎的楼层，设计一种策略使得在最坏
//情况下尝试的次数最少。
//就2个鸡蛋进行讨论
//鸡蛋在0层不会碎，策略：假设第一次选择的楼层数为q，此时如果鸡蛋碎掉，那么
//就要在1层至q-1逐层进行尝试，最坏的情况下就是q-1层不会碎，因此一共需要进行q次
//尝试，若在q层不碎，假设第二次选择的楼层数为p，此时如果鸡蛋碎掉，那么就要在
//q+1至p-1逐层进行尝试，最坏的情况下就是p-1层不会碎，因此一共需要进行2+p-1-(q+1)+1
//即p-q+1次，为了保证最坏情况下尝试次数最少，则p-q+1=q，即p应该比q高q-1层楼。
//可以这样理解：第一次没碎，因为已经尝试了一次，所以第二次选择的楼层数应该减1
//也可以这样理解：把在每一楼层数做的决策看成是树的分支，我们最终目的是希望找到
//根的左子树和右子树最短的路径，因此尽量保证该树是一棵完全二叉树，即左子树和右子树
//高度相等，假设不会碎走的是右子树，则右子树的高度为1+p-1+1-(q+1)，（右子树的高度
//=它的碎左子树+1），由1+p-1+1-(q+1) = p -1得p=2q-1
//因此有q+(q-1)+(q-2)+...+1=n，求出q向上取整
//
//动态规划解法：f(n,m)为我们所想求的结果，则f(n,1) = n; f(0,m) = 0
//f(n,m) = min< 1 <= i <= n >{max(f(i-1,m-1), f(n-i,m))}+1
//
#include<iostream>
#include<ctime>
#include<cstdlib>

using namespace std;

const int n = 1000;
const int m = 2;
int arr[n+1][m+1];
int num = 0;
//递归做法
int two_eggs(int n, int m) {
    ++num;
    
    int min = INT_MAX;

    for (int i = 1; i <= n; ++i) {
        int a, b;
        if (arr[i-1][m-1] == -1) {
            a = two_eggs(i-1,m-1);
            arr[i-1][m-1] = a;
        }
        else if (arr[i-1][m-1] == -2) {
            a = INT_MAX;
        }
        else {
            a = arr[i-1][m-1];
        }

        if (arr[n-i][m] == -1) {
            b = two_eggs(n-i,m);
            arr[n-i][m] = b;
        }
        else if (arr[n-i][m] == -2) {
            b = INT_MAX;    
        }
        else {
            b = arr[n-i][m];
        }
        int tmp = a > b ? (a+1) : (b+1);
        if (min > tmp) {
            min = tmp;
        }
    }
    return min; 
}
//非递归做法
int two_eggs_not_recursion(int n, int m) {
    
    int w[n+1][m+1];
    
    for(int j = 0; j <= m; ++j) {
        w[0][j] = 0;
    }

    for (int i = 0; i <= n; ++i) {
        w[i][1] = i;
    }
    int a, b, tmp;
    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j <= m; ++j) {
            int min = INT_MAX;
            for (int p = 1; p <= i; ++p) {
                b = w[i-p][j] + 1;
                a = w[p-1][j-1] + 1;
                tmp = a > b ? a : b;
                min = min > tmp ? tmp : min;
            }
            w[i][j] = min;
        }
    }
    return w[n][m];
    
}
int main(void) {
    clock_t start, end;
    start = clock();
    for (int i = 0; i <= n; ++i) {
        arr[i][1] = i;
        for (int j = 2; j <= m; ++j) {
            if (i == 0) {
                arr[i][j] = 0;
            }
            else {
                arr[i][j] = -1;
            }
        }
        arr[i][0] = -2;
    }
    arr[0][0] = 0;
    
    //cout << two_eggs(10000,2) << endl;
    end = clock();
    cout << "recursioin two eggs cost " << (end - start) << endl;
    cout << num << "-------------" << CLOCKS_PER_SEC <<endl;
    start = clock();
    cout << two_eggs_not_recursion(10000,20) << endl;
    end = clock();
    cout << "recursioin two eggs cost " << (end - start) << endl;
}
